#include <stdio.h>
#include <string.h>

/*
 * 完全背包
 */

#define STDIN
//#define DEBUG


int V, V1, V2;
int YN;
//V表示总额
//V1*1000表示能被用来投资的钱，必须是1000的倍数
//V2是剩余的钱，不能用来投资
//V = v1*1000 + V2

int v[15], w[15];
int bn;

int dp[50005];

#define max(a, b) (a) > (b) ? (a) : (b)

void CompletePackage(int cost, int weight)
{
    int v;
    cost /= 1000;
    for (v = cost; v <= V1/1000; v++)
    {
        dp[v] = max(dp[v], dp[v-cost]+weight);
    }
}

void process()
{
    int i;
#ifdef DEBUG
    for (i = 0; i < bn; ++i)
    {
        printf("%d %d\n", v[i], w[i]);
    }
#endif

    V2 = V % 1000;
    V1 = (V-V2);

    while(YN--)
    {
        memset(dp, 0, sizeof(dp));

        for (i = 0; i < bn; i++)
        {
            CompletePackage(v[i], w[i]);
        }
#ifdef DEBUG
        printf("dp[%d]: %d\n", V1, dp[V1/1000]);
#endif

        V = V1 + V2 + dp[V1/1000];
        V2 = V % 1000;
        V1 = (V-V2);
#ifdef DEBUG
        printf("V: %d V1: %d V2: %d\n", V, V1, V2);
#endif
    }
#ifdef DEBUG
    printf("V: %d V1: %d V2: %d\n", V, V1, V2);
#else
    printf("%d\n", V);
#endif


#ifdef DEBUG
    for (i = 0; i <= V1/1000; i++)
        printf("%d ", dp[i]);
    printf("\n");
#endif
}


int main()
{
#ifdef STDIN
    freopen("bin/2063.in", "r", stdin);
#endif

    int N, Ni;
    scanf("%d", &N);
    for (Ni = 0; Ni < N; Ni++)
    {
        scanf("%d %d", &V, &YN);
        scanf("%d", &bn);
        int bni;
        for (bni = 0; bni < bn; bni++)
        {
            scanf("%d %d", &v[bni], &w[bni]);
        }
        process();
    }
    return 0;
}
